TCAM hardware devices are commonly employed in today's high performance communication systems for fast routing lookups and packet classification. A TCAM search will compare the header of the incoming packet against all entries in the forwarding table or the classifier database in parallel. The lookup result is returned with a fixed latency regardless of record location and number of records in the TCAM.
For IPv4/v6 routing lookups the entries are sorted based on the address prefix lengths in the forwarding table in order to guarantee longest prefix matching (LPM). Keeping the entries sorted in the TCAM under addition and deletion of routing lookup entries is a time consuming operation, and may take N memory shift (delete & rewrite) operations in the worst case, where N is the number of prefixes in the forwarding table, e.g. 32 for IPv4 and 128 for IPv6. Keeping the TCAM entries sorted as such can delay data path forwarding of communications traffic and can cause a sustained load on system CPU resources, which has the potential to cause problems such as degrading system performance. The risk of performance degradation is especially high during bulk routing updates.
Allocating records in a TCAM to fixed size clusters, also referred to hereinafter as blocks, is known. However, selecting a suitable initial default block size may be difficult. For example, if the initial block size is too small for a particular application, the addition of all new entries in a block after the block becomes full may overburden CPU resources since move operations will be needed to insert each new entry. Furthermore, a system that is designed for several different markets and applications may have different IP route distribution requirements, which could mean a suitable “one size fits all” default block size per route prefix length is difficult to determine. Moreover, during periods where there are bulk routing updates, for example many routing table adds/deletes due to a major change in a network, the resulting extra processing could be CPU resource and time consuming if the route table grows large and several blocks associated with respective IP address prefix lengths approach and reach capacity.
Therefore an efficient approach for dynamically allocating records into blocks in a TCAM is desired.